\documentclass[a4paper,10pt]{article}

\usepackage{graphicx}
\usepackage[cm]{fullpage}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{cancel}
\usepackage{hyperref}
\usepackage{enumerate}

% commands for setting up the page
\parindent0mm
\pagestyle{empty}

\sloppy

% environment for "exercise"
\newcounter{exc}
\setcounter{exc}{11}
\newenvironment{exercise}[1]%
{\refstepcounter{exc}\textbf{Exercise \arabic{exc}} \emph{#1}\\}
{

\hrulefill\medskip}%

\newenvironment{solution}
{
\medskip

\textbf{Solution}

}
{ \medskip }

\renewcommand{\labelenumi}{(\alph{enumi})}

\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\vc}[1]{\boldsymbol{#1}}
\newcommand{\LP}{\mathrm{LP}}
\newcommand{\LD}{\mathrm{LD}}
\newcommand{\EX}{\mathrm{EX}}
\newcommand{\conv}{\mathrm{conv}}
\let\emptyset\varnothing

\begin{document}

%% Header
\begin{center}
  {\large \bf Exercises for\\
    Mathematical Programming\\
    186.835 VU 3.0 - SS 14}\\
  \bigskip
  Last update: \today
\end{center}

\hrulefill\medskip

Group members:
\begin{enumerate}
\item Christian Hafner, 0925172, chafner@cg.tuwien.ac.at
\item Klemens Jahrmann, 0826080, klemens.jahrmann@tuwien.ac.at
\item Kevin Streicher, 1025890, e1025890@student.tuwien.ac.at
\end{enumerate}

\hrulefill\medskip


\begin{exercise}{Bin Packing}\label{ex:bpack}
 In the bin-packing problem we are given a set of bins of capacity $W$ and a list of $n$ items of integer sizes $L=\{l_1, \dots, l_n\}$, $0\le l_j\le W$ for $1\le j\le n$. The objective is to assign the items to the bins so that the capacity of the bins is not exceeded and the number of used bins is minimized.

One classic formulation for the bin packing problem is given by \eqref{eq:bp-obj}--\eqref{eq:bp-end}. In \eqref{eq:bp-obj}--\eqref{eq:bp-end}, variables $y_i\in \{0,1\}$, $i=1,\dots, n$, indicate whether or not bin $i$ is used, while variables $x_{ij}\in \{0,1\}$, $i,j=1,\dots, n$, indicate whether or not item $j$ is assigned to bin $i$.

\begin{small}
\begin{align}
 \min \quad z = & \sum_{i=1}^n y_i \label{eq:bp-obj} \\
  \mbox{s.t.} & \sum_{j=1}^n l_j x_{ij} \le W y_i & i=1,\dots, n \\
	      & \sum_{i=1}^n x_{ij} = 1 & j=1,\dots, n \\
	& y_i\in \{0,1\} & i=1\dots, n \\
	& x_{ij}\in \{0,1\} & i,j=1\dots, n \label{eq:bp-end}
\end{align}
\end{small}

Develop a formulation for the bin packing problem that utilizes an exponential (in the number of items) number of variables.

\begin{solution}
	\input{ex12.tex}
	
\end{solution}

\end{exercise}

\begin{exercise}{Bin Packing (cont.)}\label{ex:bpack2}
Consider the formulation for the bin packing problem you developed in your solution to Exercise~\ref{ex:bpack}.
\begin{itemize}
 \item Formally state the pricing subproblem, arising when solving the LP relaxation of your formulation by column generation and describe a feasible approach for solving the pricing subproblem.
 \item Find an instance for which your extended formulation yields a better LP bound than formulation \eqref{eq:bp-obj}--\eqref{eq:bp-end}. (If no such example exists, your extended formulation may be wrong / not reasonable.)
 \item Describe a reasonable branching rule that may be used in a branch-and-price algorithm.
\end{itemize}

\begin{solution}
	\input{ex13.tex}
	
\end{solution}

\end{exercise}

\begin{exercise}{Hop Constrained STP}\label{ex:hcstp}
Consider the Hop Constrained Steiner Tree Problem (HCSTP): We are given an undirected graph $G=(V,E)$, a dedicated root node $0\in V$, a set of terminal nodes $T\subset V\setminus \{0\}$, an edge costs $c_e\ge 0$, $\forall e\in E$, and a hop limit $H\in \N$.
A feasible solution $S$ to the HCSTP is a Steiner tree containing the root node and all terminal nodes (further potential Steiner nodes may be included) which satisfies the hop constraint, i.e., the unique path from $0$ to any terminal $t\in T$ in $S$ may not contain more than $H$ edges. 
The objective is to identify a feasible solution $S^*=(V^*,E^*)$ yielding minimum total costs, i.e., $\sum_{e\in E^*} c_e$.

\begin{itemize}
 \item Provide a \emph{directed} ILP formulation for the HCSTP using an exponential number of \emph{path variables}. (Don't forget to define and describe the used variables). 
 \item Formally state the pricing subproblem. (You first need to describe which dual variables are associated to which of your constraints.)
 \item Give an interpretation of the pricing subproblem. (Which combinatorial optimization problem needs to be solved?). Can we solve pricing subproblem in polynomial time or is it NP-hard? (Hint: You may need to argue on the sign of a subset of your dual variable values.)
\end{itemize}

\begin{solution}
	\input{ex14.tex}
	
\end{solution}

\end{exercise}


\begin{exercise}{Chv\'atal-Gomory Cutting Planes}\label{ex:cg-in}
 Consider the set $X=\{(x_1,x_2)\in \Z^2 : -4x_1+6x_2\le 9, 2x_1 + 3x_2\le 10, x_1\ge 0, x_2\ge 0\}$.
Use the Chv\'atal-Gomory procedure to find a description for $\rm{conv}(X)$.

\begin{solution}
	\input{ex15.tex}
	
\end{solution}

\end{exercise}


\begin{exercise}{Cover Inequality}\label{ex:cov-in}
 Consider the knapsack set $X=\{\{0,1\}^6 : 12x_1 + 9x_2 + 7x_3 + 5x_4 + 5x_5 + 3x_6\leq 14\}$.
 \begin{itemize}
  \item[(i)] Find a minimum cover $C$ and a corresponding valid cover inequality.
  \item[(ii)] Find the extended cover inequality for $C$.
  \item[(iii)] Lift the inequality to obtain a strong valid inequality, i.e., compute all lifting coefficients. 
 \end{itemize}
 
 \begin{solution}
	\input{ex16.tex}
	
\end{solution}

 \end{exercise}

\begin{exercise}{Total\cancel{ly} Unimodularity}\label{ex:tu1}
 Prove of disprove
\begin{itemize}
 \item The node-edge incidence matrix of an undirected graph is not totally unimodular.
\\ (The node-edge incidence matrix has one column for each edge $\{i,j\}$ with entries $+1$ in rows $i$ and $j$.)
 \item The node-arc incidence matrix of a bipartite, directed graph is totally unimodular.
\\ (The node-arc incidence matrix has one column for each arc $(i,j)$ with entries $+1$ in row $i$ and $-1$ in row $j$.)
\end{itemize}

\begin{solution}
	\input{ex17.tex}
	
\end{solution}

\end{exercise}

\bibliographystyle{plain}
\bibliography{exercises3}

\end{document}
